/*
 * region_search.h
 *
 *  Created on: 03.02.2013
 *      Author: Maksim Lazeba
 */

#pragma once

#include <vector>

const int Y_DIM = 1;
const int X_DIM = 0;

using std::size_t;

struct rect_t;

struct point_t
{
	double x, y;

	point_t(double x, double y) :
			x(x), y(y)
	{
	}

	point_t(const point_t &p) :
			x(p.x), y(p.y)
	{
	}

	point_t() :
			x(0), y(0)
	{
	}

	bool smaller(const point_t &b, int dim) const;
	bool between(const point_t &a, const point_t &b, int dim) const;
	int cmp(double d, int dim) const;
};

struct rect_t
{
	point_t lb;
	point_t rt;

	rect_t(point_t &lb, point_t &rt) :
			lb(lb), rt(rt)
	{
	}
};

struct region_tree
{
	struct list_node
	{
		bool end;
		point_t point;
		size_t left_lb, left_ub, right_lb, right_ub;
		size_t position;

		list_node(const point_t &p, size_t llb, size_t lub, size_t rlb,
				size_t rub, size_t pos) :
				end(false), point(p), left_lb(llb), left_ub(lub), right_lb(rlb), right_ub(
						rub), position(pos)
		{
		}

		list_node(const point_t &p) :
				end(false), point(p), left_lb(0), left_ub(0), right_lb(0), right_ub(
						0), position(0)
		{
		}

		list_node(size_t left_end, size_t right_end, size_t pos) :
				end(true), left_lb(left_end), left_ub(left_end), right_lb(
						right_end), right_ub(right_end), position(pos)
		{
		}

		bool operator<(const point_t &b) const;
		bool operator<=(const point_t &b) const;
		bool operator<(const list_node &b) const;
	};

	struct tree_node
	{
		tree_node *left, *right;
		bool leaf;
		double lb, rb;
		std::vector<list_node> list;

		tree_node(tree_node *left, tree_node *right);
		tree_node(const point_t &point);
		~tree_node();
	};

	tree_node *root;

	typedef std::vector<list_node>::iterator list_iter;
	void add_from_region(const tree_node *node, const rect_t &rect,
			size_t lb_cur, size_t ub_cur, std::vector<point_t>& ans) const;

	region_tree(std::vector<point_t> &points);
	~region_tree();
	std::vector<point_t> get_points_in_rect(const rect_t &rect) const;
};

